10520 - Determine it/10520.cpp

   1 #include <stdio.h>
   2 #include <algorithm>
   3
   4 using namespace std;
   5
   6 #define MAXN 19
   7
   8 int n, base;
   9 long long cache[MAXN+1][MAXN+1];
  10
  11 long long a(const int &i, const int &j){
  12   if (i == n && j == 0) return 0;
  13   if (i == n && j == 1) return base;
  14
  15   if (cache[i][j] == -1){
  16     long long &r = cache[i][j] = 0;
  17
  18     if (i < j){
  19       for (int k=i; k<j; ++k){
  20         r = max(r, a(i, k) + a(k+1, j));
  21       }
  22     }else{ //i >= j
  23       long long x = 0, y = 0;
  24       if (i < n){
  25         for (int k=i+1; k<=n; ++k){
  26           x = max(x, a(k, 1) + a(k, j));
  27         }
  28       }
  29
  30       if (j > 0){
  31         for (int k=1; k<j; ++k){
  32           y = max(y, a(i, k) + a(n, k));
  33         }
  34       }
  35       r = x + y;
  36     }
  37   }
  38   return cache[i][j];
  39 }
  40
  41 int main(){
  42   while (scanf("%d %d", &n, &base) == 2){
  43     memset(cache, -1, sizeof cache);
  44     printf("%lld\n", a(1, n));
  45   }
  46   return 0;
  47 }